Exploiting RSA with Mersenne Primes

Generally speaking, RSA encryption depends on the use of randomly generated primes, and the use of primes with special characteristics can lead to easy exploits. One such example is using two Mersenne primes to generate the modulus.

Consider primes:

where we assume that \(m > n\).

Then,

To crack such a cryptosystem one just needs to consider \(N - 1 = 2^{mn} - 2^m - 2^n\), and then factor out the largest possible power of \(2\), which will necessarily be \(2^n\).

This simple procedure has found the value of \(2^n\), and hence \(2^n - 1\), one of the primes used to generate the cryptosystem. Then a simple division finds the other.

Furthermore, factoring powers of \(2\) is very easy with binary numbers, since it's just a matter of counting how many trailing zeros there are.

Example

Consider an RSA system with modulus \(N = 1040257\) which was the product of two Mersenne primes. Now, if we consider \(N - 1 = 1040256\), which is \(11111101111110000000\) in binary, it is clear that this can have a factor of \(2^7\) taken out, given the number of trailing zeros. Hence \(2^7 - 1 = 127\) is one of the primes while \(\frac{1040257}{127} = 8191\) was the other.